package william.quicksort;

import william.utils.ArrayUtils;

import java.util.Arrays;
import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author ZhangShenao
 * @date 2024/1/29
 * @description 快速排序
 * 对数组 arr[L,R] 范围内进行快速排序
 * 随机选择一个元素，并与 R 位置的元素进行交换，作为基准值。
 * 维护两个区间：小于区 [L,less] 和大于区 [more,R]，初始情况下，less = L-1，more = R。
 * -遍历数组，针对每一个元素，与基准值进行比较，分为三种情况：
 * - 该元素 == 基准值，无需任何处理，直接跳到下一个元素。
 * - 该元素 < 基准值，则将该元素与小于区的下一个元素进行交换，同时将小于区向右移动一位，并跳到下一个元素。
 * - 该元素 > 基准值，则将该元素与大于区的前一个元素进行交换，同时将大于区向左移动一位。此时不跳下一个元素，因为该元素是刚交换过来的，还没有处理过。
 * 重复上述过程，直到当前元素与大于区的第一个元素相遇。
 * 将 R 位置的元素与大于区的第一个元素交换
 * 处理完成后，会将整个数组划分成3个区域：小于区 [L,less] 、等于区[less+1, more] 和 大于区 [more+1,R]
 * 对小于区和大于区的数组递归调用上述过程，直到整个数组有序。
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArray(10, -100, 100);
        System.out.println("原始数组为: ");
        System.out.println(Arrays.toString(arr));
        quickSortIteration(arr);
        System.out.println("排序后数组为: ");
        System.out.println(Arrays.toString(arr));
        System.out.println("数组是否按照升序排列: " + ArrayUtils.isInAscOrder(arr));
    }


    /**
     * 对数组进行快速排序
     */
    public static void quickSort(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length < 2) {
            return;
        }

        //递归调用
        quickSortRecursion(arr, 0, arr.length - 1);

    }

    /**
     * 递归处理
     * 对arr[L,R]范围进行快速排序
     */
    public static void quickSortRecursion(int[] arr, int L, int R) {
        //递归终止条件
        if (L >= R) {
            return;
        }

        //进行partition操作,找到等于区的范围
        int[] equalsArea = partition(arr, L, R);

        //递归调用,对小于区和等于区分别进行快速排序
        quickSortRecursion(arr, L, equalsArea[0] - 1);
        quickSortRecursion(arr, equalsArea[1] + 1, R);
    }

    /**
     * partition过程
     * 选定基准值,将整个数组划分成小于基准值、等于基准值和大于基准值三个区域
     * 最终返回一个包含2个元素的数组,分别记录等于区域的起始索引和终止索引
     */
    public static int[] partition(int[] arr, int L, int R) {
        //随机选择一个元素,与R位置的元素进行交换,以此作为基准值
        int idx = ThreadLocalRandom.current().nextInt(L, R + 1);
        swap(arr, idx, R);
        int pivot = arr[R];

        //维护两个区域:小于区[L,less]和大于区[more,R]
        int less = L - 1;
        int more = R;

        //遍历数组,将每个元素与基准值进行比较
        int i = L;
        while (i < more) {
            int n = arr[i];
            if (n == pivot) {    //该元素=基准值,无需任何处理,直接跳到下一个元素
                i++;
            } else if (n < pivot) { //该元素<基准值,将该元素与小于区的下一个元素进行交换,同时将小于区向右移动,并跳到下一个元素
                swap(arr, ++less, i++);
            } else {    //该元素>基准值,将该元素与大于区的前一个元素进行交换,同时大于区向左移动,不跳下一个元素
                swap(arr, --more, i);
            }
        }

        //将R位置的元素与大于区的第一个元素进行交换
        swap(arr, more, R);

        //返回等于区的范围
        return new int[]{less + 1, more};
    }

    /**
     * 将数组arr中i和j索引的元素进行交换
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 非递归实现
     * 通过自己维护的栈,来代替递归调用的系统栈。
     * 每执行完一次Partition操作后,都将左、右两个区间的Partition操作作为子任务,压入栈中
     */
    public static void quickSortIteration(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length < 2) {
            return;
        }

        //自己维护一个栈,来保存子任务
        Stack<Range> tasks = new Stack<>();

        //先进行一次Partition操作,将整个数组分区,然后将左、右区间的Partition操作,分别作为子任务压栈
        int[] equalArea = partition(arr, 0, arr.length - 1);
        tasks.push(new Range(0, equalArea[0] - 1));
        tasks.push(new Range(equalArea[1] + 1, arr.length - 1));

        //持续从栈中获取子任务进行处理,直到任务栈为空
        while (!tasks.empty()) {
            //取出子任务,进行Partition操作
            Range range = tasks.pop();
            int L = range.L;
            int R = range.R;
            if (L >= R) {
                continue;
            }

            int[] eq = partition(arr, L, R);

            //将子区间继续作为子任务入栈
            tasks.push(new Range(L, eq[0] - 1));
            tasks.push(new Range(eq[1] + 1, R));
        }

    }

    /**
     * 子任务的处理范围
     */
    private static class Range {
        private int L;
        private int R;

        public Range(int l, int r) {
            L = l;
            R = r;
        }
    }
}
